package com.xigua._贪心;

import java.util.HashMap;
import java.util.Map;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2022/4/716:23
 */
public class _45_跳跃游戏_2 {

    public static void main(String[] args) {
        jump(new int[]{2,3,1,1,4});
    }

    public static int jump(int[] nums) {
        if (nums.length == 0) return 0;
        int n = nums.length-1;
        Map<Integer,Integer> hashMap = new HashMap<>();
        for (int i = n-1; i >=0 ; i--) {
             if (nums[i] >= n-i){
                 hashMap.put(i,1);
             } else{
                 int count = Integer.MAX_VALUE;
                 if (nums[i] == 0) {
                     hashMap.put(i, 10000);
                    continue;
                 }
                 for (int j = i+1; j <= i+nums[i]; j++) {
                    count= Math.min(hashMap.get(j),count);
                 }
                 count++;
                 hashMap.put(i,count);
             }
        }
        return hashMap.get(0);
    }

    public int jump1(int[] nums) {
        int position = nums.length - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }


}
